package practice1_100;

public class Practice337 {
    TreeNode count=new TreeNode(-1);

    public int rob(TreeNode root) {
        int sum=0;
        //sum=dp(root,count);
        if(root==null) return 0;
        else if(root.left!=null && root.right!=null){
//            count.left=new TreeNode(-1);
//            count.right=new TreeNode(-1);
            sum=Math.max(rob(root.left)+rob(root.right),root.val+rob(root.left.left)+rob(root.right.left)+rob(root.left.right)+rob(root.right.right));

        }else if(root.left!=null && root.right==null){
            sum=Math.max(rob(root.left),root.val+rob(root.left.left)+rob(root.left.right));
        }else if(root.left==null && root.right!=null){
            sum=Math.max(rob(root.right),root.val+rob(root.right.left)+rob(root.right.right));
        }else if(root.left==null && root.right==null){
            sum= root.val;
        }

        return sum;


    }
    //root为要遍历的树，node作为参考
    public int dp(TreeNode root,TreeNode node){
        int sum=0;
        if(root==null) return 0;
        else if(root.left!=null && root.right!=null){
            if(count.val!=-1) return count.val;
            count.left=new TreeNode(-1);
            count.right=new TreeNode(-1);
            count.right.right=new TreeNode(-1);
            count.right.left=new TreeNode(-1);
            count.left.right=new TreeNode(-1);
            count.left.left=new TreeNode(-1);
            sum=Math.max(dp(root.left,count.left)+dp(root.right,count.right),root.val+dp(root.left.left,count.left.left)+dp(root.right.left,count.right.left)+dp(root.left.right,count.left.right)+dp(root.right.right,count.right.right));
            count.val=sum;
        }else if(root.left!=null && root.right==null){
            if(count.val!=-1) return count.val;

            count.left=new TreeNode(-1);
            count.left.right=new TreeNode(-1);
            count.left.left=new TreeNode(-1);
            sum=Math.max(dp(root.left,count.left),root.val+dp(root.left.left,count.left.left)+dp(root.left.right,count.left.right));
            count.val=sum;

        }else if(root.left==null && root.right!=null){
            if(count.val!=-1) return count.val;
            count.right=new TreeNode(-1);
            count.right.right=new TreeNode(-1);
            count.right.left=new TreeNode(-1);
            sum=Math.max(dp(root.right,count.right),root.val+dp(root.right.left,count.right.left)+dp(root.right.right,count.right.right));
            count.val=sum;

        }else if(root.left==null && root.right==null){
            if(count.val!=-1) return count.val;
            sum= root.val;
            count.val=sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        //[3,2,3,null,3,null,1]
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.right=new TreeNode(3);
        root.right.right=new TreeNode(1);

        int a=new Practice337().rob(root);
        System.out.println(a);
    }
}

 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
        this.right = right;
    }
 }
